package newBee.class1;

import common.ArrayUtils;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/next-greater-element-ii/description/
 * 下一个更大元素ii
 * 解题思路：
 * 1.遍历两边，第二遍取%的值
 */
public class Code02_nextGreaterElementII {
    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
        int[] ans = nextGreaterElements(arr);
        ArrayUtils.printArr(ans);
    }

    public static int[] nextGreaterElements(int[] arr) {
        int r = 0, n = arr.length;
        int[] stack = new int[2 * n], ans = new int[n];
        Arrays.fill(ans, -1);

        // 遍历两遍，就能循环找到所有下标的下一个更大的数
        for (int i = 0; i < 2 * n; i++) {
            int t = i % n;
            while (r > 0 && arr[stack[r - 1]] < arr[t]) {
                int k = stack[--r];
                ans[k] = arr[t];
            }
            stack[r++] = t;
        }
        return ans;
    }
}
